#define _CRT_SECURE_NO_WARNINGS 1
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        if (pHead == NULL)return NULL;
        ListNode* p1 = (ListNode*)malloc(sizeof(struct ListNode));
        ListNode* p2 = (ListNode*)malloc(sizeof(struct ListNode));
        ListNode* star1 = p1;
        ListNode* star2 = p2;
        ListNode* cur = pHead;
        while (cur) {
            if (cur->val < x) {
                p1->next = cur;
                p1 = p1->next;
            }
            else {
                p2->next = cur;
                p2 = p2->next;
            }
            cur = cur->next;
        }
        p1->next = star2->next;
        p2->next = NULL;
        ListNode* t = star1->next;
        free(star2);
        free(star1);
        star2 = NULL;
        star1 = NULL;
        return t;

    }